// 深度优先遍历
//1.深度优先遍历的递归写法
function deepTraversal(node) {
    let nodes = [];
    if (node != null) {
        nodes.push[node]; // 存放每个节点，判断
        let childrens = node.children; // 判断是否有子 有则继续
        for (let i = 0; i < childrens.length; i++)
            deepTraversal(childrens[i]);
    }
    return nodes;
}

// 广度优先遍历

// function wideTraversal(node){
//     let nodes=[],i=0;
//     if(node!=null){
//         nodes.push(node);
//         wideTraversal(node.nextElementSibling); 
//         node=nodes[i++];
//         wideTraversal(node.firstElementChild);
//     }
//     return nodes;
// }


// https://img-blog.csdn.net/20180705160341166?watermark/2/text/aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3pqeV9hbmRyb2lkX2Jsb2c=/font/5a6L5L2T/fontsize/400/fill/I0JBQkFCMA==/dissolve/70
function dfs(root,fVisit){
    let stack = Array.isArray(root) ? [...root] : [root];
    while(stack.length){
        let node = stack.pop(); // 那最后一个[current ]
        fVisit && fVisit(node);
        let children = node.children;
        if(children && children.length){  // [zi, zi, ] // 子永远先被用
            for(let i=children.length-1;i>=0;i--) stack.push(children[i]); // 倒着放先进后出
        }
    }
}


// https://img-blog.csdn.net/20180705155854774?watermark/2/text/aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3pqeV9hbmRyb2lkX2Jsb2c=/font/5a6L5L2T/fontsize/400/fill/I0JBQkFCMA==/dissolve/70
function bfs(root, fVisit) {
    let queue = Array.isArray(root) ? [...root] : [root];
    while (queue.length) {
        let node = queue.shift(); // 拿的是第一个
        fVisit && fVisit(node); // 存放同层级的
        let children = node.children; // 有子则把子按顺序放入queue 形成一个数组
        if (children && children.length) {
            for (let i = 0; i < children.length; i++) queue.push(children[i]);
        }
    }
}

//验证数组转树
let a = array2Tree(arr, null);
console.log(a);

//验证树转数组
let a1 = [];
bfs(a, node => a1.push(node));
console.log(a1);